package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/08/16 18:49
 **/
public class Day31_4_Num56_Merge {
    class Solution {
        public int[][] merge(int[][] intervals) {
            int len = 0;
            for(int[] arr : intervals){
                if(arr[0] > len) len = arr[0];
                if(arr[1] > len) len = arr[1];
            }
            // new 一个新数组，长度是intervals 最大值的两倍，把intervals范围内的数*2填入数组
            // 【避免出现[1,3][4,5]，3和4中间是未覆盖部分，转化为[2,6][8,10]，6和8不连续】
            int[] data = new int[(len+1)*2];
            for(int[] arr : intervals){
                for(int i = arr[0]*2;i <= arr[1]*2;i++){
                    data[i] = 1;
                }
            }
            List<int[]> res = new ArrayList<>();
            for(int i = 0;i < data.length;i++){
                if(data[i] == 1){   // 如果连续为1，则肯定是覆盖后的范围
                    int start = i/2;
                    while(i < data.length && data[i] == 1){
                        i++;
                    }
                    int end = (i-1)/2;
                    res.add(new int[]{start, end});
                }
            }
            return res.toArray(new int[res.size()][2]);
        }
    }
}